package code;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.Stack;
import java.util.Vector;


public class WordBreakII {
	 public List<String> wordBreak(String s, Set<String> dict) {
	        Iterator<String> it = dict.iterator();
	        int n=s.length();
	        boolean[] dp=new boolean[n+1];
	        
	        String subStr;
	        /*
	         * dp[i]表示0~i是否能组成单词
	         * dp[i]由dp[j]与[j...i]一起决定j<=i
	         * 同时vv[i]记录能所有的j的位置，[j...i]能组成单词
	         */
	        ArrayList<ArrayList<Integer>> vv=new ArrayList<ArrayList<Integer>>(n+1);
	        int i,j,k;
	        vv.add(null);
	        dp[0]=true;
	        for(i=1;i<=n;i++){
	        	dp[i]=false;
	        	vv.add(new ArrayList<Integer>());
	        	for(j=0;j<i;j++){
	        		//subString(j,i)只能取到[j...i-1]的字符
	        		subStr=s.substring(j, i);
	        		if(dict.contains(subStr)){
	        			//[j...i]能组成单词的话，那么dp[j][i]=|dp[j-1][i]
	        			if(j==0 || dp[j]){
	        				dp[i]=true;
	        				vv.get(i).add(j);
	        			}
	        		}
	        	}
	        }
	        dfsTraverse(s,dp,n,vv);
	        return ans;
	    }
	 
	 private List ans=new ArrayList<String>();
	 private Stack<Integer> stack=new Stack<Integer>();
	 
	 public void dfsTraverse(String s,boolean[] dp,int v,ArrayList<ArrayList<Integer>> vv){
		 if(v==0){
			 List<Integer> list=new ArrayList<Integer>();
			 while(!stack.empty()){
				 list.add(stack.peek());
				 stack.pop();
			 }
			 for(int i=list.size()-1;i>=0;i--){
				 stack.push(list.get(i));
			 }
			 System.out.print("---- > ");
			 int k=0;
			 StringBuilder sb=new StringBuilder();
			 for(int i=0;i<list.size();i++){
				 System.out.print(s.substring(k,list.get(i))+"  ");
				 
				 sb.append(s.substring(k,list.get(i)));
				 if(i!=list.size()-1)	sb.append(" ");
				 k=list.get(i);
			 }
			 System.out.println(sb);
			 ans.add(sb.toString());
			 System.out.println("\n");
			 return ;
		 }
		 stack.push(v);
		 for(int i=0;i<vv.get(v).size();i++){
			 if(dp[vv.get(v).get(i)])
				 dfsTraverse(s,dp,vv.get(v).get(i), vv);
		 }
		 stack.pop();
	 }
	 public static void main(String[] args){
		 WordBreakII wb=new WordBreakII();
		 String s="catsanddog";
		 Set set=new HashSet<String>();
		 set.add("cat");
		 set.add("cats");
		 set.add("and");
		 set.add("sand");
		 set.add("dog");
		 System.out.println(wb.wordBreak(s, set));
	 }
}
